package editor.cn;

import javax.xml.stream.events.EndDocument;

class Solution213{
    public static void main(String[] args) {
        Solution solution = new Solution213().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public int rob(int[] nums) {
        if (nums.length==1)return nums[0];
        if (nums.length==2)return Math.max(nums[0],nums[1]);

        //方案一。将环形转化为非环形。
        //return dp1(nums);
        //方案二。灵神的，最优的解决方案。（各种复杂度都最低）
        return Math.max(nums[0]+dp2(nums,2, nums.length-1), dp2(nums,1, nums.length));//取和没取nums[0]


    }
        private int dp1(int[] nums) {
            int n = nums.length;
            int[] dp1 = new int[n];
            //与第一题相比，转化核心就在于首尾处。考虑头取还是不取即可。
            //取nums[0],尾巴就不能取，转化为2~n-2之间的版本I问题
            dp1[0]=nums[0];
            dp1[1]=nums[0];
            for (int i = 2; i < n-1; i++) {
                dp1[i]=Math.max(dp1[i-1],dp1[i-2]+nums[i]);
            }

            //不取nums[0],尾巴就能取到，转化为3~n-1之间的版本I问题
            int[] dp2 = new int[n];
            dp2[0]=0;
            dp2[1]=nums[1];
            for (int i = 2; i < n; i++) {
                dp2[i]=Math.max(dp2[i-1],dp2[i-2]+nums[i]);
            }
            return Math.max(dp1[n-2],dp2[n-1]);
        }

        private int dp2(int[] nums,int start,int end){
            int f0=0;//代表截止dp[j]前面的第二个的总和
            int f1=0;//代表截止dp[j]前面的第一个的总和
            for (int i = start; i < end; i++) {
                int newF=Math.max(f1,f0+nums[i]);
                f0=f1;
                f1=newF;
            }
            return f1;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}












